package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/binary-tree-tilt/description
 *
 * 题型： 二叉树的后序遍历 + 求和
 *
 * ```
 * 563. 二叉树的坡度
 *
 * 给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。
 *
 * 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
 *
 * 整个树 的坡度就是其所有节点的坡度之和。
 *
 *
 * 示例 1：
 * 输入：root = [1,2,3]
 * 输出：1
 * 解释：
 * 节点 2 的坡度：|0-0| = 0（没有子节点）
 * 节点 3 的坡度：|0-0| = 0（没有子节点）
 * 节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
 * 坡度总和：0 + 0 + 1 = 1
 *
 * 示例 2：
 * 输入：root = [4,2,9,3,5,null,7]
 * 输出：15
 * 解释：
 * 节点 3 的坡度：|0-0| = 0（没有子节点）
 * 节点 5 的坡度：|0-0| = 0（没有子节点）
 * 节点 7 的坡度：|0-0| = 0（没有子节点）
 * 节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）
 * 节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）
 * 节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）
 * 坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15
 *
 * 示例 3：
 * 输入：root = [21,7,14,1,1,2,2,3,3]
 * 输出：9
 *
 * ```
 */
class leetcode_563 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val root: TreeNode = n1
        n1.left = n2
        n1.right = n3
        val actual = findTilt(root)
        val expected = 1
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        // 4,2,9,3,5,null,7
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n7 = TreeNode(7)
        val n9 = TreeNode(9)

        val root: TreeNode = n4
        n4.left = n2
        n4.right = n9
        n2.left = n3
        n2.right = n5
        n9.right = n7
        val actual = findTilt(root)
        val expected = 15
        Assert.assertEquals(expected, actual)
    }

    private fun findTilt(root: TreeNode?): Int {
        /**
        题型：二叉树的后序遍历
        思路：
        当前节点的总和（重点） = 当前节点 + 它的左子树总和 + 它的右子树总和
        当前节点坡度 = 当前节点的(左子树总和-右子树总和) 的绝对值
        整个树 的坡度 = 节点坡度的累加
        https://www.bilibili.com/video/BV1vs4y1t7FB/
        https://mp.weixin.qq.com/s?__biz=MzU0ODMyNDk0Mw==&mid=2247495262&idx=1&sn=85c3d3339341d989e6b875767caa069e&chksm=fb427d7ecc35f46893a4189c937198a15e4d2f9cc87f1797d4d297a178ff45c2c534f5d9a99f&scene=27
         */
        f(root)
        return totalTilt
    }

    var totalTilt: Int = 0
    private fun f(root: TreeNode?): Int {
        // 1 确定函数参数以及返回值
        // 返回值：当前节点总和

        // 2 确定终止条件
        if (null == root) {
            // println("root=null")
            return 0
        }

        // 3 确定单层递归的遍历逻辑：左右中
        // 左
        val leftSum = f(root.left)

        // 右
        val rightSum = f(root.right)

        // 中
        // 求当前节点的坡度
        val currentTilt: Int = Math.abs(leftSum - rightSum)

        // 更新全局变量的坡度和
        totalTilt = totalTilt + currentTilt
        // 当前节点和 = 当前节点 + 左节点和 + 右节点和
        val currentSum: Int = root.`val` + leftSum + rightSum
        // println("${root.`val`} => currentSum=$currentSum, leftSum=$leftSum, rightSum=$rightSum, currentTilt=$currentTilt,totalTilt=$totalTilt")

        println("${root.`val`},currentTilt=$currentTilt, leftSum=$leftSum, rightSum=$rightSum，currentSum=¥currentSum")

        // 返回当前节点和
        return currentSum
    }
}